package leetcode每日一题;

/**
 * 1. 问题描述
 *   用以太网线缆将n台计算机连接成一个网络，计算机的编号从0到n-1。线缆用connections表示，
 *   其中connections[i] = [a, b]连接了计算机a和b。
 *   网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
 *   给你这个计算机网络的初始布线connections，你可以拔开任意两台直连计算机之间的线缆，
 *   并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回-1
 *
 * 2. 算法分析
 *      1. 并查集
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 连接网络的最小数量 {
    // 定义并查集
    class UnionFind {
        int[] root;
        int[] rank;
        int maxsize;
        int conns;

        public UnionFind(int n) {
            maxsize = n;
            root = new int[n];
            rank = new int[n];
            for(int i = 0; i < n; i++) {
                root[i] = i;
                rank[i] = 0;
            }
            conns = n;
        }

        public int find(int x) {
            if(root[x] == x) {
                return x;
            }
            return find(root[x]);
        }

        public void union(int x,int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) {
                if(rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                }
                else if(rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                }
                else if(rank[rootX] == rank[rootY]) {
                    root[rootY] = rootX;
                    rank[rootX]++;
                }
                conns--;
            }
        }
    }

    // 求出最小连接数
    public int makeConnected(int n, int[][] connections) {
        int connCounts = connections.length; // 缆线的数量
        // n个节点至少需要n-1个缆线来连接
        if(connCounts < n- 1) {
            return -1;
        }
        // 创建并查集合，构建并查集，计算出环的数量，并且找出环中的节点
        boolean[] visited = new boolean[n];
        UnionFind uf = new UnionFind(n);
        int circles = 0;
        for(int i = 0; i < connCounts; i++) {
            int cp1 = connections[i][0];
            int cp2 = connections[i][1];
            visited[cp1] = true;
            visited[cp2] = true;
            int root1 = uf.find(cp1);
            int root2 = uf.find(cp2);
            if(root1 == root2) {
                circles++;
            }
            uf.union(cp1,cp2);
        }
        return uf.conns - 1;
    }
}
